We present a parallelizable SSOR preconditioning scheme for Krylov subspace iterative solvers which proves to be efficient in lattice QCD applications involving Wilson fermions. Our preconditioner is based on a locally lexicographic ordering of the lattice points. In actual hybrid Monte Carlo applications with the bi-conjugate gradient stabilized method BiCGstab, we achieve a gain factor of about 2 in the number of iterations compared to conventional odd-even preconditioning. Whether this translates into similar reductions in run time will depend on the parallel computer in use. We discuss implementation issues using the `Eisenstat-trick' and machine specific advantages of the method for the APE100/Quadrics parallel computer. In a full QCD simulation with Wilson fermions on a 512-processor Quadrics QH4 we find a gain in cpu-time of a factor of 1.7 over odd-even preconditioning for a 24^3 x 40 lattice.